// scaup - Scala up!
// (c) 2008-2010, Normen Müller, normen.mueller@gmail.com  
// $Id: E.scala 78 2010-05-13 12:25:41Z normen.mueller $
package scaup.eq

/** 
 *  @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 *  @version 0.0.4
 */
case class EquivalenceSpecification(val name: String, val alternatives: Map[String, Alternatives], val unordered: Set[String]) {
  override def toString = 
    ( "equivspec " + name + "{\n"
    + ((alternatives map (_ match {
        case (elem, alt) => if(unordered contains elem) "unordered element " + elem + alt else "element " + elem + alt 
      })) mkString "\n")
    + "\n}"
    )  
}

/** 
 *  @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 *  @version 0.0.4
 * 
 *  @todo alts should be a set rather than a list (due to potential dublicates)
 */
case class Alternatives(constraints: List[Constraints]) {
  override def toString = constraints match {
    case Nil               => "{}"
    case constraint :: Nil => constraint.toString
    case _                 => "{" + "alternative {" + (constraints mkString " ") + "}}"
  }
}

/** 
 *  @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 *  @version 0.0.4
 */
case class Constraints(reqAnnos: Set[String], optAnnos: Set[String], reqOrdConsts: Set[String], optOrdConsts: Set[String], reqUOrdConsts: Set[String], optUOrdConsts: Set[String]) {
  override def toString =
    ( "{"
    + (if(! (reqAnnos.isEmpty && optAnnos.isEmpty))
         "annotations{" + (reqAnnos mkString ",") + (optAnnos mkString "?,") + "}" +
           (if(reqOrdConsts.isEmpty && optOrdConsts.isEmpty && reqUOrdConsts.isEmpty && optUOrdConsts.isEmpty) "" else " ") // a bit of beautifying
       else "")
    + (if(! (reqOrdConsts.isEmpty && optOrdConsts.isEmpty && reqUOrdConsts.isEmpty && optUOrdConsts.isEmpty))
         ("constituents{"
         + (if(reqOrdConsts.isEmpty && optOrdConsts.isEmpty) "" else "ordered{" + (reqOrdConsts mkString ",") + (optOrdConsts mkString "?,") + "}")
         + (if(reqUOrdConsts.isEmpty && optUOrdConsts.isEmpty) "" else "unordered{" + (reqUOrdConsts mkString ",") + (optUOrdConsts mkString "?,") + "}")
         + "}"
         )
       else "")    
    + "}"
    )
}

/** 
 *  @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 *  @version 0.0.4
 */
case class Slit[T](val before: Option[Seq[T]],val focus: Option[T],val after: Seq[T])
  
/** An equivalence system.
 * 
 *  <p>An equivalence system is a set of equivalence relations.</p>
 * 
 *  <p>For further information please refer to:<br/>
 *  Normen M&#xFC;ller, Change Management on Semi-Structured Documents, PhD thesis<br/>
 *  School of Engineering & Science, Jacobs University Bremen, Campus Ring 1, 28759 Bremen, Germany</p>
 * 
 *  @devnote Why contravariant type constructor? If <code>S <: T</code> then <code>E[T] <: E[S]</code> wrt. the cardinality of equal elements.
 *    For example, <code>XML <: AnyRef</code> but within the equivalence system of XML more elements are considers to be equal than within
 *    the equivalence system of AnyRef.
 *
 *  @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 *  @version 0.0.4
 */
trait EquivalenceSystem[M <: {def get(key: String): Option[Seq[T]]}, -T] {  
  val alternatives: Map[String, Alternatives]
  
  def ordered(l: String): Boolean
  
  def nameOf[S <: T](l: S): String
  
  def annotationsOf[S <: T](l: S): M
  
  def constituentsOf[S <: T](l: S): Seq[S]
  
  private def equiv[S <: T](l: S, r: S): Boolean =
    if(nameOf(l) == nameOf(r)) alternatives.get(nameOf(l)) match {
      case Some(Alternatives(Nil))  => true                   // equal by name
      case Some(Alternatives(alts)) => compareTo(alts, l, r)  // equal by spec
      case None                     => l == r                 // equal by XML deep equality 
    } else false 
  
  private def equivSeq[S <: T](l: List[S], r: List[S]): Boolean =
    if(l.size == r.size) (l, r) match {
      case (lhd :: ltl, rhd :: rtl) => equiv(lhd, rhd) && equivSeq(ltl, rtl)
      case (Nil, Nil)               => true
      case _                        => false
    } else false
  
  private def equivSet[S <: T](l: List[S], r: List[S]): Boolean = 
    (  (l.size == r.size)
    && (l.elements forall (le => r.elements exists (re => equiv(le, re))))
    )
    
  private def compareTo[S <: T](alts: List[Constraints], l: S, r: S): Boolean = alts match {
    case hd :: tl =>
      (  (compareAnnos(hd.reqAnnos, hd.optAnnos, l, r))
      && (compareConsts(hd.reqOrdConsts, hd.reqUOrdConsts, hd.optOrdConsts, hd.optUOrdConsts, l, r))
      ) || compareTo(tl, l, r)
    case Nil      => false
  }
  
  private def compareAnnos[S <: T](reqAnnos: Set[String], optAnnos: Set[String], l: S, r: S): Boolean =
    (  (reqAnnos forall (a => (annotationsOf(l).get(a), annotationsOf(r).get(a)) match {
          case (Some(la), Some(ra)) => la == ra
          case _                    => false
        }))
    && (optAnnos forall (a => (annotationsOf(l).get(a), annotationsOf(r).get(a)) match {    	
    	  case (Some(la), Some(ra)) => la == ra
    	  case _                    => true          
    	}))
    )
  
  private def compareConsts[S <: T](reqOC: Set[String], reqUC: Set[String], optOC: Set[String], optUC: Set[String], l: S, r: S): Boolean =    
    (
       ((  (reqOC forall (label => (constituentsOf(l) exists (nameOf(_) == label)) && (constituentsOf(r) exists (nameOf(_) == label))))
        && (equivSeq(constituentsOf(l).toList filter (reqOC contains nameOf(_)), constituentsOf(r).toList filter (reqOC contains nameOf(_))))
       ))      
    &&
       ((  (reqUC forall (label => (constituentsOf(l) exists (nameOf(_) == label)) && (constituentsOf(r) exists (nameOf(_) == label))))
        && (equivSet(constituentsOf(l).toList filter (reqUC contains nameOf(_)), constituentsOf(r).toList filter (reqUC contains nameOf(_))))
       ))
    &&
       (((exoptOC: Set[String]) =>
         equivSeq(constituentsOf(l).toList filter (exoptOC contains nameOf(_)), constituentsOf(r).toList filter (exoptOC contains nameOf(_)))
       )(optOC filter (label => (constituentsOf(l) exists (nameOf(_) == label)) && (constituentsOf(r) exists (nameOf(_) == label)))))
    &&
       (((exoptUC: Set[String]) =>
        equivSet(constituentsOf(l).toList filter (exoptUC contains nameOf(_)), constituentsOf(r).toList filter (exoptUC contains nameOf(_)))
       )(optUC filter (label => (constituentsOf(l) exists (nameOf(_) == label)) && (constituentsOf(r) exists (nameOf(_) == label)))))
    )
  
  def findEquivTo[S <: T](elem: S, ctx: Seq[S]): Slit[S] = findEquivTo(elem, ctx, Nil)
  
  private def findEquivTo[S <: T](elem: S, ctx: Seq[S], acc: Seq[S]): Slit[S] = ctx match {
    case Nil | Seq.empty =>
      Slit(None,None,acc)      
    case _ if equiv(elem,ctx(0)) =>
      if(ordered(nameOf(elem))) acc match {
        case Nil | Seq.empty => Slit(None, Some(ctx(0)), ctx.drop(1))
        case _               => Slit(Some(acc), Some(ctx(0)), ctx.drop(1))
      } else Slit(None, Some(ctx(0)),acc ++ ctx.drop(1))      
    case _ =>
      findEquivTo(elem, ctx.drop(1), acc ++ Seq(ctx(0)))
  }  
}
